#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e6+7;
const int Mod=1e9+7;
int T;
ll A,B,C;

int low[Maxn],minp[Maxn];

vector<int>prm;
bitset<Maxn>isp;

inline int Gcd(int x,int y){
    return !y?x:Gcd(y,x%y);
}
inline void init(int N){
    for(int i=1;i<=N;i++) low[i]=1;
    for(int i=2;i<=N;i++){
        if(!isp.test(i)){
            prm.emplace_back(i);
            minp[i]=1;
            for(int j=i+i;j<=N;j+=i){
                isp.set(j);
                int x=j,c=0;
                while(!(x%i)) x/=i,c++;
                minp[j]=Gcd(minp[j],c);
            }
        }
    }
    for(int i=2;i<=N;i++){
        if(!isp.test(i)){
            low[i]=i;
            for(int j=i+i;j<=N;j+=i){
                int x=j,c=0;
                while(!(x%i)) x/=i,c++;
                c/=minp[j];
                for(int k=1;k<=c;k++) low[j]*=i;
            }
        }
    }
}

int main(){
    freopen("alien.in","r",stdin);
    freopen("alien.out","w",stdout);
    init(1e6);

    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld",&A,&B,&C);
        ll ans=0;
        for(ll i=2;i<=B;i++){
            ll pp=low[i];
            for(ll pk=pp,l=1;pk<=A;pk*=pp,l++){
                
                if(pk==i) continue;
                if(pk*minp[i]%l==0 and pk*minp[i]/l<=C){
                    ans++;
                    // cout<<pk<<" "<<i<<" "<<pk*minp[i]/l<<endl;
                }
                if((__int128)pk*pp>A) break;
            }
        }
        // for(int i=1;i<=A;i++)
        //     for(int j=1;j<=B;j++)
        //         for(int k=1;k<=C;k++)
        //             if(pow(j,i)==pow(i,k))
        //                 ans++,cout<<i<<' '<<j<<' '<<k<<endl;
        
        printf("%lld\n",(ans+C+min(A,min(B,C))-1)%Mod);
    }

    system("pause");
    return 0;
}
/*
3
1 2 3
3 4 5
6 7 8

2
99 9999 99999
2000 20000 200000

*/